{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Array into Fibonacci Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitIntoFibonacci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组拆分成斐波那契序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数字字符串 <code>num</code>，比如 <code>\"123456579\"</code>，我们可以将它分成「斐波那契式」的序列 <code>[123, 456, 579]</code>。</p>\n",
    "\n",
    "<p>形式上，<strong>斐波那契式&nbsp;</strong>序列是一个非负整数列表 <code>f</code>，且满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= f[i] &lt; 2<sup>31</sup></code>&nbsp;，（也就是说，每个整数都符合 <strong>32 位</strong>&nbsp;有符号整数类型）</li>\n",
    "\t<li><code>f.length &gt;= 3</code></li>\n",
    "\t<li>对于所有的<code>0 &lt;= i &lt; f.length - 2</code>，都有 <code>f[i] + f[i + 1] = f[i + 2]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 <code>0</code> 本身。</p>\n",
    "\n",
    "<p>返回从 <code>num</code> 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 <code>[]</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = \"1101111\"\n",
    "<strong>输出：</strong>[11,0,11,11]\n",
    "<strong>解释：</strong>输出[110,1,111]也可以。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>num = \"112358130\"\n",
    "<strong>输出: </strong>[]\n",
    "<strong>解释: </strong>无法拆分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\"0123\"\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>每个块的数字不能以零开头，因此 \"01\"，\"2\"，\"3\" 不是有效答案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 200</code></li>\n",
    "\t<li><code>num</code>&nbsp;中只含有数字</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-array-into-fibonacci-sequence](https://leetcode.cn/problems/split-array-into-fibonacci-sequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-array-into-fibonacci-sequence](https://leetcode.cn/problems/split-array-into-fibonacci-sequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1101111\"', '\"112358130\"', '\"0123\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ret=[]\n",
    "        def dfs(index: int):\n",
    "            if index==len(num):\n",
    "                return len(ret)>=3\n",
    "            cur=0\n",
    "            for i in range(index, len(num)):\n",
    "                if i>index and num[index]=='0':\n",
    "                    break\n",
    "                cur=cur*10+ord(num[i])-ord('0')\n",
    "                if(cur>2**31-1): break\n",
    "                if(len(ret)>=2):\n",
    "                    if cur<ret[-1]+ret[-2]:\n",
    "                        continue\n",
    "                    elif cur>ret[-1]+ret[-2]:\n",
    "                        break\n",
    "                ret.append(cur)\n",
    "                if dfs(i+1):\n",
    "                    return 1\n",
    "                ret.pop()\n",
    "            return 0\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\r\n",
    "\r\n",
    "        l=len(num)\r\n",
    "        if l<3:\r\n",
    "            return []\r\n",
    "        nums=list(map(int,num))\r\n",
    "        if l==3:\r\n",
    "            return nums[0]+nums[1]==nums[2]\r\n",
    "\r\n",
    "        ret=[]\r\n",
    "        Max=2**31\r\n",
    "        def dfs(idx):\r\n",
    "            nonlocal l,ret\r\n",
    "            if idx==l:\r\n",
    "                if len(ret)>2:\r\n",
    "                    return True\r\n",
    "                return False\r\n",
    "            cur=0\r\n",
    "            \r\n",
    "            for i in range(idx,l):\r\n",
    "                if i>idx and nums[idx]==0:\r\n",
    "                    break\r\n",
    "                cur=cur*10+nums[i]\r\n",
    "                if cur>=Max:\r\n",
    "                    return False\r\n",
    "                if len(ret)<2:\r\n",
    "                    ret.append(cur)\r\n",
    "                    if dfs(i+1):\r\n",
    "                        return True\r\n",
    "                    ret.pop()\r\n",
    "                else:\r\n",
    "                    target=ret[-1]+ret[-2]\r\n",
    "                    if cur==target:\r\n",
    "                        ret.append(cur)\r\n",
    "                        if dfs(i+1):\r\n",
    "                            return True\r\n",
    "                        ret.pop()\r\n",
    "                    if cur>target:\r\n",
    "                        return False\r\n",
    "            return False\r\n",
    "        dfs(0)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        path = []\n",
    "        n = len(num)\n",
    "        def backTracking(start):\n",
    "            if path and path[-1]>=2**31: #越界\n",
    "                return False\n",
    "            if start == n and len(path)>=3:\n",
    "                return True\n",
    "            for i in range(start, n):\n",
    "                if num[start] == '0' and i > start:\n",
    "                    break\n",
    "                digit = int(num[start:i + 1])\n",
    "                if len(path) >= 2 and digit != path[-1] + path[-2]:\n",
    "                    continue\n",
    "                path.append(digit)\n",
    "                if backTracking(i + 1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            return False\n",
    "        \n",
    "        backTracking(0)\n",
    "        return path\n",
    "                    \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        # 官方————回溯 + 剪枝\n",
    "        def backtrack(pos):\n",
    "            if pos == n:\n",
    "                return len(res) >= 3\n",
    "            Sum = 0\n",
    "            for i in range(pos,n):\n",
    "                # 下面是对应的三种剪枝操作判断\n",
    "                if i > pos and num[pos] == \"0\":\n",
    "                    break\n",
    "                Sum = Sum * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if Sum > 2 ** 31 - 1:\n",
    "                    break\n",
    "                if len(res) < 2 or Sum == res[-2] + res[-1]:\n",
    "                    res.append(Sum)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    res.pop()\n",
    "                elif len(res) > 2 and Sum > res[-2] + res[-1]:\n",
    "                    break\n",
    "            return False\n",
    "\n",
    "        res = []\n",
    "        n = len(num)\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = list()\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            \n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2**31 - 1:\n",
    "                    break\n",
    "                \n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "        \n",
    "            return False\n",
    "        \n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "      n = len(num)\n",
    "      def backtrack(cur, temp_state):\n",
    "        if len(temp_state)>=3 and cur == n:\n",
    "          self.res = temp_state\n",
    "          return \n",
    "      \n",
    "        if cur == n:\n",
    "          return \n",
    "\n",
    "        for i in range(cur,n) :\n",
    "          if num[cur]==\"0\" and i>cur: # 数字0 开头 跳过\n",
    "              return \n",
    "          if  int(num[cur:i+1])>2 ** 31 -1 or int(num[cur:i+1])<0:\n",
    "            continue\n",
    "          if len(temp_state)<2:\n",
    "            backtrack(i+1,temp_state+[int(num[cur:i+1])])\n",
    "          else :\n",
    "            if int(num[cur:i+1])==temp_state[-1]+temp_state[-2]:\n",
    "              backtrack(i+1,temp_state+[int(num[cur:i+1])])\n",
    "      \n",
    "\n",
    "      self.res = []\n",
    "      backtrack(0,[])\n",
    "\n",
    "      return self.res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def dfs(lst, num_):\n",
    "            if num_ == \"\": return lst, \"\"\n",
    "            if len(lst) <= 1:\n",
    "                if num_[0] == '0': return dfs(lst + [0], num_[1:]) \n",
    "                for i in range(1, len(num_) - 1):\n",
    "                    lst_, s = dfs(lst + [int(num_[:i])], num_[i:])\n",
    "                    if s == \"\": return lst_, s \n",
    "            else:\n",
    "                x = lst[-2] + lst[-1]\n",
    "                if x < 1 << 31 and num_.startswith(s_ := str(x)): return dfs(lst + [x], num_[len(s_): ])\n",
    "            return lst, num_\n",
    "        lst, s = dfs([], num)\n",
    "        return [] if s else lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, x: str) -> List[int]:\n",
    "        res = list()\n",
    "        def dfs(st):\n",
    "            if st == len(x):\n",
    "                return len(res) >= 3\n",
    "            c = 0\n",
    "            for i in range(st, len(x)):\n",
    "                if i > st and x[st] == '0':\n",
    "                    break\n",
    "                c = c * 10 + ord(x[i]) - ord('0')\n",
    "                if c > 2**31 - 1:\n",
    "                    break\n",
    "                if len(res) >= 2:\n",
    "                    if c < res[-1] + res[-2]:\n",
    "                        continue\n",
    "                    elif c > res[-1] + res[-2]:\n",
    "                        break \n",
    "                res.append(c)\n",
    "                if dfs(i + 1):\n",
    "                    return True\n",
    "                res.pop()\n",
    "            return False\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = list()\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            \n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2**31 - 1:\n",
    "                    break\n",
    "                \n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "        \n",
    "            return False\n",
    "        \n",
    "        backtrack(0)\n",
    "        return ans\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        # 官方————回溯 + 剪枝\n",
    "        def backtrack(pos):\n",
    "            if pos == n:\n",
    "                return len(res) >= 3\n",
    "            Sum = 0\n",
    "            for i in range(pos,n):\n",
    "                # 下面是对应的三种剪枝操作判断\n",
    "                if i > pos and num[pos] == \"0\":\n",
    "                    break\n",
    "                Sum = Sum * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if Sum > 2 ** 31 - 1:\n",
    "                    break\n",
    "                if len(res) > 2 and Sum > res[-2] + res[-1]:\n",
    "                    break\n",
    "                elif len(res) < 2 or Sum == res[-2] + res[-1]:\n",
    "                    res.append(Sum)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    res.pop()\n",
    "            return False\n",
    "\n",
    "        res = []\n",
    "        n = len(num)\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        res = []\n",
    "        i_current = 0\n",
    "        self.res_success = []\n",
    "        self.len_num = len(num)\n",
    "        self.num_max = 2**31\n",
    "        self.dfs(num, i_current, res)\n",
    "        return self.res_success\n",
    "\n",
    "    def dfs(self, num, i_current, res):\n",
    "        # print('i: %d, res: %s' % (i_current, str(res)))\n",
    "        # condition return success\n",
    "        if i_current == self.len_num:\n",
    "            if len(res) >= 3:  # at least 3 num to construct fibonacci\n",
    "                # save result and return\n",
    "                self.res_success = res.copy()\n",
    "            else:\n",
    "                # directly return, undo main when all sub done\n",
    "                pass\n",
    "            return\n",
    "        # condition return fail\n",
    "        if i_current > self.len_num:\n",
    "            # directly return, undo main when all sub done\n",
    "            return\n",
    "            \n",
    "        for j_current in range(i_current + 1, self.len_num + 1):\n",
    "            # continue next sub problem\n",
    "            num_next = int(num[i_current: j_current])\n",
    "            num_in_range = (num_next < self.num_max)\n",
    "            if not num_in_range:\n",
    "                return\n",
    "            \n",
    "            num_next_start = int(num[i_current: i_current + 1])\n",
    "            start_with_zero = (num_next_start == 0 and j_current - i_current > 1)\n",
    "            if start_with_zero:\n",
    "                return\n",
    "            if len(res) < 2 or (res[-2] + res[-1] == num_next): # condition next sub problem valid\n",
    "                # do current step\n",
    "                res.append(num_next)\n",
    "                # solve next sub problem\n",
    "                self.dfs(num, j_current, res)\n",
    "\n",
    "                # undo current step\n",
    "                res.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        LIMIT = 2 ** 31 - 1\n",
    "        n = len(num)\n",
    "        for i in range(min(10, n)):\n",
    "            if i > 0 and num[0] == '0':\n",
    "                break\n",
    "            for j in range(i + 1, min(10, n)):\n",
    "                if j > i + 1 and num[i + 1] == '0':\n",
    "                    break\n",
    "                num1 = int(num[:i+1])\n",
    "                num2 = int(num[i+1:j+1])\n",
    "                num3 = num1 + num2\n",
    "                num3_str = str(num3)\n",
    "                res = [num1, num2]\n",
    "                k = j + 1\n",
    "                while k < n:\n",
    "                    num3 = num1 + num2\n",
    "                    num3_str = str(num3)\n",
    "                    if num3 > LIMIT or num[k:k+len(num3_str)] != num3_str:\n",
    "                        break\n",
    "                    res.append(num3)\n",
    "                    num1, num2 = num2, num3\n",
    "                    k += len(num3_str)\n",
    "                else:\n",
    "                    if len(res) >= 3:\n",
    "                        return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        def trackback(index):\n",
    "            if index == len(num):\n",
    "                # 判断是否有三个以上的数\n",
    "                return len(ans) >= 3\n",
    "\n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == '0':\n",
    "                    # 以0开头的非0的数不符和要求\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2 ** 31 - 1:\n",
    "                    # 数字过大不符合要求\n",
    "                    break\n",
    "\n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    # 满足斐波那契数列的要求\n",
    "                    ans.append(curr)\n",
    "                    if trackback(i+1):\n",
    "                        return True\n",
    "                    ans.pop() # 回溯\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "            return False\n",
    "        trackback(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        for i in range(1, n - 2):\n",
    "            for j in range(i + 1, n - 1):\n",
    "                ans.clear()\n",
    "                if (num[0] != '0' or i == 1) and (num[j] != '0' or j == i + 1) and int(num[:i]) < 2 ** 31 \\\n",
    "                        and int(num[i:j]) < 2 ** 31:\n",
    "                    ans += [int(num[:i]), int(num[i:j])]\n",
    "                    next_num = int(num[:i]) + int(num[i:j])\n",
    "                    p = 0\n",
    "                    q = i\n",
    "                    r = j\n",
    "                    while r < n and next_num < 2 ** 31 and num[r:].startswith(str(next_num)):\n",
    "                        ans.append(next_num)\n",
    "                        p, q, r = q, r, r + len(str(next_num))\n",
    "                        next_num = int(num[p:q]) + int(num[q:r])\n",
    "                    if r == n:\n",
    "                        return ans\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def dfs(lst, num_):\n",
    "            if num_ == \"\": \n",
    "                return lst, \"\"\n",
    "            if len(lst) <= 1:\n",
    "                if num_[0] == '0': return dfs(lst + [0], num_[1:]) \n",
    "                for i in range(1, len(num_) - 1):\n",
    "                    lst_, s = dfs(lst + [int(num_[:i])], num_[i:])\n",
    "                    if s == \"\": return lst_, s \n",
    "            else:\n",
    "                x = lst[-2] + lst[-1]\n",
    "                if x < 1 << 31 and num_.startswith(s_ := str(x)):\n",
    "                    #print(lst + [x], num_[len(str(x)): ])\n",
    "                    return dfs(lst + [x], num_[len(s_): ])\n",
    "            return lst, num_\n",
    "        lst, s = dfs([], num)\n",
    "        #print(lst, s)\n",
    "        return [] if s else lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = list()\n",
    "        def back(index):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == '0':\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord('0')\n",
    "                if curr > 2 ** 31 - 1:\n",
    "                    break\n",
    "                if len(ans) < 2 or curr == ans[-1] + ans[-2]:\n",
    "                    ans.append(curr)\n",
    "                    if back(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-1] + ans[-2]:\n",
    "                    break\n",
    "            return False\n",
    "        back(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\r\n",
    "\r\n",
    "        def check(n:str) -> bool:\r\n",
    "            return n == \"0\" or n[0] != '0'     \r\n",
    "        n = len(num)\r\n",
    "        for i in range(n - 2):\r\n",
    "            for j in range(i + 1, n - 1):\r\n",
    "                res = []\r\n",
    "                n0, n1 = num[:i + 1], num[i + 1:j + 1]\r\n",
    "                if not check(n0) or not check(n1):\r\n",
    "                    continue\r\n",
    "                res.append(n0)\r\n",
    "                res.append(n1)\r\n",
    "                cur = j + 1\r\n",
    "                flag = True\r\n",
    "                while cur != n:\r\n",
    "                    s = str(int(n0) + int(n1))\r\n",
    "                    if cur + len(s) > n or num[cur:cur+len(s)] != s:\r\n",
    "                        flag = False\r\n",
    "                        break\r\n",
    "                    res.append(s)\r\n",
    "                    cur += len(s)\r\n",
    "                    n0, n1 =  n1, int(s)\r\n",
    "                if flag:\r\n",
    "                    res =  list(map(int, res))\r\n",
    "                    if max(res) < (1 << 31):\r\n",
    "                        return res\r\n",
    "        return []\r\n",
    "                    \r\n",
    "\r\n",
    "            \r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, S: str) -> List[int]:\n",
    "        def backtrack(start, path):\n",
    "            # 剪枝1\n",
    "            if len(path) > 2 and path[-1] != path[-2] + path[-3]:\n",
    "                return []\n",
    "            if start >= len(S):\n",
    "                if len(path) > 2:\n",
    "                    return path\n",
    "                return []\n",
    "\n",
    "            cur = 0\n",
    "            ans = []\n",
    "            # 枚举分割点\n",
    "            for i in range(start, len(S)):\n",
    "                # 剪枝2\n",
    "                if i > start and S[start] == '0':\n",
    "                    return []\n",
    "                cur = cur * 10 + int(S[i])\n",
    "                # 剪枝3\n",
    "                if cur > 2**31 - 1:\n",
    "                    return []\n",
    "                path.append(cur)\n",
    "                ans = backtrack(i + 1, path)\n",
    "                # 剪枝 4\n",
    "                if len(ans) > 2:\n",
    "                    return ans\n",
    "                path.pop()\n",
    "            return ans\n",
    "\n",
    "        return backtrack(0, [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, S: str) -> List[int]:\n",
    "        n, up = len(S), 2147483647\n",
    "\n",
    "        def get_list(start):\n",
    "            # 判断前面两个数会不会超过上限\n",
    "            if max(li) > up:\n",
    "                return False\n",
    "\n",
    "            # 遍历后面所有的字符串看看能不能组成斐波那契，\n",
    "            # 如果 数超上限 或 最后一个数超字符串长度 或 字符串并不是下一个数 则直接跳出\n",
    "            while start < n:\n",
    "                now = li[-1] + li[-2]\n",
    "                c = len(str(now))\n",
    "                if now > up or start + c > n or int(S[start:start + c]) != now:\n",
    "                    return False\n",
    "                li.append(now)\n",
    "                start += c\n",
    "            return True\n",
    "\n",
    "        for i in range(1, 11):\n",
    "            # 这里让j取不到字符串末尾最后一位，顺便如果两个字符串有个是0开始的，直接只跑0的情况\n",
    "            for j in range(1, min(11, n - i)):\n",
    "                li = [int(S[:i]), int(S[i:i + j])]\n",
    "                if get_list(i + j):\n",
    "                    return li\n",
    "                if S[i] == '0':\n",
    "                    break\n",
    "            if S[0] == '0':\n",
    "                break\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        path = []\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == len(num) and len(path) > 2:\n",
    "                ans = path[:]\n",
    "                return\n",
    "            \n",
    "            for r in range(i + 1, len(num) + 1):\n",
    "                if (num[i] == '0' and r > i + 1) or int(num[i:r]) >= 2**31:\n",
    "                    break\n",
    "                \n",
    "                if len(path) < 2:\n",
    "                    path.append(int(num[i:r]))\n",
    "                    dfs(r)\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    first, second = path[-2], path[-1]\n",
    "                    if int(num[i:r]) == first + second:\n",
    "                        path.append(int(num[i:r]))\n",
    "                        dfs(r)\n",
    "                        path.pop()\n",
    "            \n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        res = []\n",
    "        def dfs(i):\n",
    "            curr = 0\n",
    "            if i == n:\n",
    "                return len(res) >= 3\n",
    "            for j in range(i,n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break \n",
    "                curr = curr * 10 + int(num[j])\n",
    "                if curr >= 2 ** 31:\n",
    "                    break\n",
    "                if len(res) < 2 or res[-1] + res[-2] == curr:\n",
    "                    res.append(curr)\n",
    "                    if dfs(j+1):\n",
    "                        return True \n",
    "                    res.pop()\n",
    "                elif len(res) >= 2 and res[-1] + res[-2] < curr:\n",
    "                    break\n",
    "            return False\n",
    "        dfs(0)\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = list()\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            \n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2**31 - 1:\n",
    "                    break\n",
    "                \n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "        \n",
    "            return False\n",
    "        \n",
    "        backtrack(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def dfs(lst, num_):\n",
    "            if num_ == \"\": \n",
    "                return lst, \"\"\n",
    "            if len(lst) <= 1:\n",
    "                if num_[0] == '0': return dfs(lst + [0], num_[1:]) \n",
    "                for i in range(1, len(num_) - 1):\n",
    "                    lst_, s = dfs(lst + [int(num_[:i])], num_[i:])\n",
    "                    if s == \"\": return lst_, s \n",
    "            else:\n",
    "                x = lst[-2] + lst[-1]\n",
    "                if x < 1 << 31 and num_.startswith(s_ := str(x)):\n",
    "                    #print(lst + [x], num_[len(str(x)): ])\n",
    "                    return dfs(lst + [x], num_[len(s_): ])\n",
    "            return lst, num_\n",
    "        lst, s = dfs([], num)\n",
    "        #print(lst, s)\n",
    "        return [] if s else lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(index):\n",
    "            if index==len(num):\n",
    "                return len(ans)>=3\n",
    "\n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i>index and num[index]==\"0\":\n",
    "                    break\n",
    "                curr = curr*10 + ord(num[i])-ord(\"0\")\n",
    "                if curr>2**31 -1:\n",
    "                    break\n",
    "                \n",
    "                if len(ans)<2 or curr==ans[-2]+ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i+1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans)>2 and curr > ans[-2]+ans[-1]:\n",
    "                    break\n",
    "\n",
    "            return False\n",
    "        \n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        fibo=[]\n",
    "        def backtrack(index):\n",
    "            if index==len(num) and len(fibo)>=3:\n",
    "                return True\n",
    "            for i in range (index,len(num)):\n",
    "                if num[index]=='0' and i>index:\n",
    "                    break\n",
    "                n=int(num[index:i+1])\n",
    "                if n > 2**31-1:\n",
    "                    break\n",
    "                if len(fibo) < 2 or n == fibo[-1] + fibo[-2]:\n",
    "                    fibo.append(n)\n",
    "                    if backtrack(i+1):\n",
    "                        return True\n",
    "                    fibo.pop()\n",
    "                if len(fibo) >= 2 and n > fibo[-1] + fibo[-2]:\n",
    "                    break\n",
    "            return False\n",
    "        backtrack(0)\n",
    "        return fibo\n",
    "\n",
    "  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ln = len(num)\n",
    "        MAX_NUM = 2 ** 31 - 1\n",
    "        MAX_lEN = len(str(MAX_NUM))  # 10位\n",
    "        \n",
    "        def backtracking(index: int, temp: list[int]) -> list[int]:\n",
    "            if len(temp) >= 3:\n",
    "                if temp[-1] != temp[-2] + temp[-3]:\n",
    "                    return\n",
    "                if index == ln:\n",
    "                    return temp[:]\n",
    "            # 寻找当前数的末尾\n",
    "            for i in range(index, ln):\n",
    "                if i != index and num[index] == \"0\":\n",
    "                    break\n",
    "                if int(num[index: i + 1]) > MAX_NUM:\n",
    "                    break\n",
    "                temp.append(int(num[index: i + 1]))\n",
    "                ans = backtracking(i + 1, temp)\n",
    "                if ans:\n",
    "                    return ans\n",
    "                temp.pop()\n",
    "            \n",
    "        ans = backtracking(0, [])\n",
    "        if not ans:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n",
    "                \n",
    "\n",
    "        \n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        path = []\n",
    "        n = len(num)\n",
    "        def backTracking(start):\n",
    "            if start == n and len(path)>=3:\n",
    "                return True\n",
    "            for i in range(start, n):\n",
    "                if num[start] == '0' and i > start:\n",
    "                    break\n",
    "                digit = int(num[start:i + 1])\n",
    "                if digit>=2**31: #越界\n",
    "                    break\n",
    "                if len(path) >= 2 and digit > path[-1] + path[-2]: #后面只会越来越大 因此提前终止\n",
    "                    break\n",
    "                if len(path) >= 2 and digit < path[-1] + path[-2]:\n",
    "                    continue\n",
    "                path.append(digit)\n",
    "                if backTracking(i + 1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            return False\n",
    "        \n",
    "        backTracking(0)\n",
    "        return path\n",
    "                    \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        def dfs(cur, i):\n",
    "            nonlocal ans\n",
    "            if len(ans):\n",
    "                return\n",
    "            if i == n:\n",
    "                if len(cur) >= 5:\n",
    "                    ans = cur[:]\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                s3 = num[i:j+1]\n",
    "                if len(s3) > 1 and num[i] == '0':\n",
    "                    break\n",
    "                if int(s3) >= (1 << 31):\n",
    "                    break\n",
    "                if cur[-1] == -1 or cur[-2] == -1 or cur[-1] + cur[-2] == int(s3):\n",
    "                    cur.append(int(s3))\n",
    "                    dfs(cur, j + 1)\n",
    "                    cur.pop()\n",
    "        cur = [-1,-1] \n",
    "        dfs(cur, 0)\n",
    "        # print(f'{ans}')\n",
    "        return ans[2:] if len(ans) >= 5 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def backtrack(index, sequence):\n",
    "            if index == len(num):\n",
    "                return len(sequence) >= 3\n",
    "            \n",
    "            for i in range(index, len(num)):\n",
    "                if num[index] == '0' and i > index:\n",
    "                    break\n",
    "                \n",
    "                val = int(num[index:i+1])\n",
    "                \n",
    "                if val > 2**31 - 1:\n",
    "                    break\n",
    "                \n",
    "                size = len(sequence)\n",
    "                \n",
    "                if size >= 2 and val > sequence[size-1] + sequence[size-2]:\n",
    "                    break\n",
    "                \n",
    "                if size < 2 or val == sequence[size-1] + sequence[size-2]:\n",
    "                    sequence.append(val)\n",
    "                    \n",
    "                    if backtrack(i+1, sequence):\n",
    "                        return sequence\n",
    "                    \n",
    "                    sequence.pop()\n",
    "            \n",
    "            return []\n",
    "        \n",
    "        result = backtrack(0, [])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = list()\n",
    "        def backtrack(index: int):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2**31 - 1:\n",
    "                    break\n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "            return False\n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        la=len(num) // 2\n",
    "        l = len(num)\n",
    "        lim =2147483647\n",
    "        def getlist(start):\n",
    "            while start<l:\n",
    "                c = li[-1]+li[-2]\n",
    "                lc = len(str(c))\n",
    "                if start+lc>l or int(num[start:start+lc]) != c or c>lim:\n",
    "                    return False\n",
    "                else:\n",
    "                    start+=lc\n",
    "                    li.append(c)\n",
    "            return True\n",
    "\n",
    "        for i in range(1,min(la+1,11)):\n",
    "            if num[0]=='0' and i!=1:\n",
    "                break\n",
    "            for j in range(1,min(l-i,la+1,11)):\n",
    "                if num[i]=='0' and j != 1:\n",
    "                    break\n",
    "                li = [int(num[:i]),int(num[i:i+j])]\n",
    "                if getlist(i+j):\n",
    "                    return li\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(index):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2 ** 31 - 1:\n",
    "                    break\n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if dfs(i+1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            \n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2 ** 31 - 1:\n",
    "                    break\n",
    "                \n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "        \n",
    "            return False\n",
    "        \n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        fibo=[]\n",
    "        def backtrack(index):\n",
    "            if index==len(num) and len(fibo)>=3:\n",
    "                return True\n",
    "            for i in range (index,len(num)):\n",
    "                if num[index]=='0' and i>index:\n",
    "                    break\n",
    "                n=int(num[index:i+1])\n",
    "                if n > 2**31-1:\n",
    "                    break\n",
    "                if len(fibo) < 2 or n == fibo[-1] + fibo[-2]:\n",
    "                    fibo.append(n)\n",
    "                    if backtrack(i+1):\n",
    "                        return True\n",
    "                    fibo.pop()\n",
    "                if len(fibo) >= 2 and n > fibo[-1] + fibo[-2]:\n",
    "                    break\n",
    "            return False\n",
    "        backtrack(0)\n",
    "        return fibo\n",
    "\n",
    "  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        length=len(num)\n",
    "        if(length<3):return []\n",
    "        def check(i,j,num): #第一个数长i，第二个数长j\n",
    "            # print(i,j)\n",
    "            length=len(num)\n",
    "            if(i+j>len(num)):return False\n",
    "            if(num[0]=='0' and i>1):return False\n",
    "            if(num[i]=='0' and j>1):return False\n",
    "            num1=int(num[0:i])\n",
    "            num2=int(num[i:j+i])\n",
    "            k=j+i\n",
    "            while(k<len(num)):\n",
    "                num3=num1+num2\n",
    "                tmp_len=len(str(num3))\n",
    "                if(tmp_len+k>len(num)):return False\n",
    "                tmp=int(num[k:k+tmp_len])\n",
    "                if(num[k]==0 and tmp_len>1):return False\n",
    "                if(tmp!=num3):return False\n",
    "                if(num3>int('7FFFFFFF',16)):return False\n",
    "                num1=num2\n",
    "                num2=num3\n",
    "                k=k+tmp_len\n",
    "            return True\n",
    "\n",
    "        for i in range(1,length-2):\n",
    "            for j in range(1,length-i):\n",
    "                if(check(i,j,num)):\n",
    "                    ans=[]\n",
    "                    num1=int(num[0:i])\n",
    "                    num2=int(num[i:j+i])\n",
    "                    ans.append(num1)\n",
    "                    ans.append(num2)\n",
    "                    k=j+i\n",
    "                    while(k<len(num)):\n",
    "                        num3=num1+num2\n",
    "                        ans.append(num3)\n",
    "                        tmp_len=len(str(num3))\n",
    "                        num1=num2\n",
    "                        num2=num3\n",
    "                        k=k+tmp_len\n",
    "                    return ans\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        lst = []\n",
    "        def dfs(i):\n",
    "            if i == n or ans:\n",
    "                if not ans and len(lst) > 2:\n",
    "                    ans.append(lst.copy())\n",
    "                return \n",
    "            if len(lst) < 2:  # 枚举\n",
    "                if num[i] == '0':\n",
    "                    lst.append(0)\n",
    "                    dfs(i + 1)\n",
    "                    lst.pop()\n",
    "                else:\n",
    "                    for j in range(i, n):\n",
    "                        lst.append(int(num[i:j + 1]))\n",
    "                        dfs(j + 1)\n",
    "                        lst.pop()\n",
    "            else:  # 下一个数已经确定\n",
    "                l = len(str(lst[-1] + lst[-2]))\n",
    "                nxt = int(num[i:i+l])\n",
    "                if nxt == lst[-1] + lst[-2] and nxt <= ((1 << 31) - 1):\n",
    "                    lst.append(nxt)\n",
    "                    dfs(i + l)\n",
    "                    lst.pop()\n",
    "                else:\n",
    "                    return\n",
    "        dfs(0)\n",
    "        return ans[0] if ans else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ln = len(num)\n",
    "        MAX_NUM = 2 ** 31 - 1\n",
    "        MAX_lEN = len(str(MAX_NUM))  # 10位\n",
    "        \n",
    "        def backtracking(index: int, temp: list[int]) -> list[int]:\n",
    "            if index == ln:\n",
    "                if len(temp) >= 3:\n",
    "                    return temp\n",
    "                return []\n",
    "            # 寻找当前数的末尾\n",
    "            for i in range(index, ln):\n",
    "                if i != index and num[index] == \"0\":\n",
    "                    break\n",
    "                if int(num[index: i + 1]) > MAX_NUM:\n",
    "                    break\n",
    "                current = int(num[index: i + 1])\n",
    "                if len(temp) < 2 or current == temp[-1] + temp[-2]:\n",
    "                    temp.append(current)\n",
    "                    ans = backtracking(i + 1, temp)\n",
    "                    if ans:\n",
    "                        return ans\n",
    "                    temp.pop()\n",
    "                elif len(temp) >= 2 and current > temp[-1] + temp[-2]:\n",
    "                    break\n",
    "            \n",
    "            return []\n",
    "            \n",
    "        return backtracking(0, [])\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        res = []\n",
    "        i_current = 0\n",
    "        self.res_success = []\n",
    "        self.len_num = len(num)\n",
    "        self.num_max = 2**31\n",
    "        self.dfs(num, i_current, res)\n",
    "        return self.res_success\n",
    "\n",
    "    def dfs(self, num, i_current, res):\n",
    "        # print('i: %d, res: %s' % (i_current, str(res)))\n",
    "        # condition return success\n",
    "        if i_current == self.len_num:\n",
    "            if len(res) >= 3:\n",
    "                # save result and return\n",
    "                self.res_success = res.copy()\n",
    "            else:\n",
    "                # directly return, undo main when all sub done\n",
    "                pass\n",
    "            return\n",
    "        # condition return fail\n",
    "        if i_current > self.len_num:\n",
    "            # directly return, undo main when all sub done\n",
    "            return\n",
    "        else:\n",
    "            for j_current in range(i_current + 1, self.len_num + 1):\n",
    "                # continue next sub problem\n",
    "                num_next = int(num[i_current: j_current])\n",
    "                num_in_range = (num_next < self.num_max)\n",
    "                if not num_in_range:\n",
    "                    return\n",
    "                else:\n",
    "                    num_next_start = int(num[i_current: i_current + 1])\n",
    "                    start_with_zero = (num_next_start == 0 and j_current - i_current > 1)\n",
    "                    if start_with_zero:\n",
    "                        return\n",
    "                    else:\n",
    "                        if len(res) < 2 or (res[-2] + res[-1] == num_next): # condition next sub problem valid\n",
    "                            # do current step\n",
    "                            res.append(num_next)\n",
    "                            # solve next sub problem\n",
    "                            self.dfs(num, j_current, res)\n",
    "            \n",
    "                            # undo current step\n",
    "                            res.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    stack = []\n",
    "    def splitIntoFibonacci(self, num):\n",
    "        def findret(index):\n",
    "            if index == len(num) and len(self.stack) >= 3:\n",
    "                return True\n",
    "            cur = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == '0':\n",
    "                    break\n",
    "                cur = cur * 10 + int(num[i])\n",
    "                if cur > 2 ** 31 - 1:\n",
    "                    break\n",
    "                if len(self.stack) <= 1 or cur == self.stack[-2] + self.stack[-1]:\n",
    "                    self.stack.append(cur)\n",
    "                    if findret(i + 1):\n",
    "                        return True\n",
    "                    self.stack.pop()\n",
    "                elif len(self.stack) > 2 and cur > self.stack[-2] + self.stack[-1]:\n",
    "                    break\n",
    "            return False\n",
    "        self.stack = []\n",
    "        if findret(0):\n",
    "            return self.stack\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        #回溯算法\n",
    "        path=[]\n",
    "        n=len(num)\n",
    "        def back(i):\n",
    "            if i==n:\n",
    "                return len(path)>=3\n",
    "            cur=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]==\"0\":\n",
    "                    break\n",
    "                cur=cur*10+int(num[j])\n",
    "                if cur>2**31-1:\n",
    "                    break\n",
    "                if len(path)<2 or cur==path[-1]+path[-2]:\n",
    "                    path.append(cur)\n",
    "                    if back(j+1):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                elif len(path)>2 and cur>path[-1]+path[-2]:\n",
    "                    break\n",
    "            return False\n",
    "        flag=back(0)\n",
    "        return path if flag else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def backtrack(num:str, res, index: int):\n",
    "            if index == len(num) and len(res) >= 3:\n",
    "                return True\n",
    "            for i in range(index, len(num)):\n",
    "                if num[index] == '0' and i > index:\n",
    "                    break\n",
    "                dig = eval(num[index:i + 1])\n",
    "                if dig > 2**31 - 1:\n",
    "                    break\n",
    "                n = len(res)\n",
    "                if n >= 2 and dig > res[n - 1] + res[n - 2]:\n",
    "                    break\n",
    "                if n <= 1 or dig == res[n - 1] + res[n - 2]:\n",
    "                    res.append(dig)\n",
    "                    if(backtrack(num,res,i + 1)):\n",
    "                        return True\n",
    "                    res.pop()\n",
    "            return False\n",
    "        res = []\n",
    "        if backtrack(num,res,0):\n",
    "            return res\n",
    "        else:\n",
    "            return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = []\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def check(ans, cur):\n",
    "            if len(ans) < 2:\n",
    "                return True\n",
    "            else:\n",
    "                return cur < 2**31 and ans[-1] + ans[-2] == cur\n",
    "        def split(cur, res, ans):\n",
    "            if self.ans:\n",
    "                return\n",
    "            if res == \"\":\n",
    "                rec = True\n",
    "                if cur != \"\" and check(ans, int(cur)):\n",
    "                    ans = ans + [int(cur)]\n",
    "                else:\n",
    "                    rec = False\n",
    "                if len(ans) >= 3 and rec:\n",
    "                    self.ans = ans\n",
    "                return\n",
    "            if cur == \"0\":\n",
    "                if check(ans, 0):\n",
    "                    split(\"\", res, ans + [0])\n",
    "            else:\n",
    "                split(cur + res[0], res[1:], ans)\n",
    "                if len(cur) > 0 and check(ans, int(cur)):\n",
    "                    split(\"\", res, ans + [int(cur)])\n",
    "        split(\"\",num,[])\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        seq = []\n",
    "\n",
    "        def helper(i):\n",
    "            \n",
    "            if i >= n:\n",
    "                return False\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                if num[i] == '0' and j > i:\n",
    "                    return False\n",
    "                a = int(num[i:j+1])\n",
    "                if a > 2**31-1:\n",
    "                    continue\n",
    "                if len(seq) < 2 or a == seq[-1] + seq[-2]:\n",
    "                    seq.append(a)\n",
    "                    if len(seq)>=3 and j == n-1:\n",
    "                        return True\n",
    "                    res = helper(j+1)\n",
    "                    if res:\n",
    "                        return True\n",
    "                    seq.pop()\n",
    "            return False\n",
    "        \n",
    "        if helper(0):\n",
    "            return seq\n",
    "        return []\n",
    "        \n",
    "                    \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        ans = list()\n",
    "\n",
    "        def backtrack(index: int):\n",
    "            if index == len(num):\n",
    "                return len(ans) >= 3\n",
    "            \n",
    "            curr = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == \"0\":\n",
    "                    break\n",
    "                curr = curr * 10 + ord(num[i]) - ord(\"0\")\n",
    "                if curr > 2**31 - 1:\n",
    "                    break\n",
    "                \n",
    "                if len(ans) < 2 or curr == ans[-2] + ans[-1]:\n",
    "                    ans.append(curr)\n",
    "                    if backtrack(i + 1):\n",
    "                        return True\n",
    "                    ans.pop()\n",
    "                elif len(ans) > 2 and curr > ans[-2] + ans[-1]:\n",
    "                    break\n",
    "        \n",
    "            return False\n",
    "        \n",
    "        backtrack(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def valid(s):\n",
    "            if not s or int(s)>2**31-1:\n",
    "                return False\n",
    "            if s[0] != 0 or s == '0':\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def check(secondStart, secondEnd):\n",
    "            thirdEnd = 0\n",
    "            ans = []\n",
    "            first, second, third = num[:secondStart], num[secondStart: secondEnd], ''\n",
    "            while thirdEnd < len(num):\n",
    "                if not valid(first) or not valid(second):\n",
    "                    return []\n",
    "                third = str(int(first) + int(second))\n",
    "                if not valid(third):\n",
    "                    return []\n",
    "                thirdEnd = secondEnd + len(third)\n",
    "                if num[secondEnd: thirdEnd] != third:\n",
    "                    return []\n",
    "                secondStart = secondEnd\n",
    "                secondEnd = thirdEnd\n",
    "                ans.append(first)\n",
    "                first = second\n",
    "                second = third\n",
    "            if (len(\"\".join(ans)) != len(num) - len(second)):\n",
    "                ans.append(first)\n",
    "            ans.append(second)\n",
    "            return ans\n",
    "\n",
    "        for secondStart in range(1, len(num)-2):\n",
    "            for secondEnd in range(secondStart, len(num)-1):\n",
    "                if ans := check(secondStart, secondEnd):\n",
    "                    return [int(c) for c in ans]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "\n",
    "        def helper(string):\n",
    "            if len(string) > 1 and string[0] == '0':\n",
    "                return False\n",
    "            if int(string) >= 2147483648:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        def dfs(x1, x2, string, path):\n",
    "            if not string:\n",
    "                res.append(path)\n",
    "                return\n",
    "\n",
    "            for i in range(1, len(string)+1):\n",
    "                x3 = string[:i]\n",
    "                if not helper(x3): return \n",
    "                if x1 + x2 == int(x3):\n",
    "                    dfs(x2, int(x3), string[i:], path+[int(x3)])\n",
    "        \n",
    "        res = []\n",
    "        n = len(num)\n",
    "        x1, x2, x3 = -1, -1, -1\n",
    "        for i in range(1, n):\n",
    "            x1 = num[:i]\n",
    "            if not helper(x1): continue\n",
    "            for j in range(i+1, n):\n",
    "                x2 = num[i:j]\n",
    "                if not helper(x2): break\n",
    "                dfs(int(x1), int(x2), num[j:], [int(x1), int(x2)])\n",
    "        return res[0] if res else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        lst = []\n",
    "        def dfs(i):\n",
    "            if i == n or ans:\n",
    "                if not ans and len(lst) > 2:\n",
    "                    ans.append(lst.copy())\n",
    "                return \n",
    "            if len(lst) < 2:  # 枚举\n",
    "                if num[i] == '0':\n",
    "                    lst.append(0)\n",
    "                    dfs(i + 1)\n",
    "                    lst.pop()\n",
    "                else:\n",
    "                    for j in range(i, n):\n",
    "                        lst.append(int(num[i:j + 1]))\n",
    "                        dfs(j + 1)\n",
    "                        lst.pop()\n",
    "            else:  # 下一个数已经确定\n",
    "                l = len(str(lst[-1] + lst[-2]))\n",
    "                nxt = int(num[i:i+l])\n",
    "                if nxt == lst[-1] + lst[-2] and nxt < ((1 << 31) - 1):\n",
    "                    lst.append(nxt)\n",
    "                    dfs(i + l)\n",
    "                    lst.pop()\n",
    "                else:\n",
    "                    return\n",
    "        dfs(0)\n",
    "        return ans[0] if ans else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self) :\n",
    "        self.ans = []\n",
    "        self.path = []\n",
    "        \n",
    "    def dfs(self, nums) :\n",
    "        # empty \n",
    "        if len(self.path) >= 3:\n",
    "            if self.path[-1] != self.path[-2] + self.path[-3]:\n",
    "                return \n",
    "\n",
    "        if not nums:\n",
    "            if len(self.path) >= 3:                     # NOTE(royfu): 有效解\n",
    "                self.ans.append(self.path.copy())\n",
    "            return \n",
    "\n",
    "        # normal \n",
    "        n = len(nums)\n",
    "        for i in range(n): \n",
    "            if str(int(nums[: i+1])) != nums[: i+1]: continue \n",
    "            num = int(nums[: i+1])\n",
    "            if num > 1 << 31: continue\n",
    "           \n",
    "            self.path.append(num)\n",
    "            self.dfs(nums[i+1:])\n",
    "            self.path.pop()\n",
    "        \n",
    "\n",
    "    def splitIntoFibonacci(self, S: str) -> List[int]:\n",
    "        self.dfs(S)\n",
    "\n",
    "        if not self.ans: return []\n",
    "        return self.ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        res = []\n",
    "        def backtrack(i):\n",
    "            if i == len(num):\n",
    "                return len(res) >= 3\n",
    "            cur = 0\n",
    "            for j in range(i, len(num)):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                cur = cur * 10 + int(num[j])\n",
    "                if cur > 2 ** 31 - 1:\n",
    "                    break\n",
    "                if len(res) < 2 or cur == res[-1] + res[-2]:\n",
    "                    res.append(cur)\n",
    "                    if backtrack(j + 1):\n",
    "                        return True\n",
    "                    res.pop()\n",
    "                elif len(res) > 2 and cur > res[-1] + res[-2]:\n",
    "                    break\n",
    "            return False\n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def GetF(self,p):\n",
    "        path = []\n",
    "        if len(p[3])==0:\n",
    "            num = p[1]\n",
    "            for i in range(len(num)):\n",
    "                n = int(num[:i + 1:])\n",
    "                if str(n)!=num[:i + 1:] or n>2**31:break\n",
    "                for j in range(i + 1, len(num)):\n",
    "                    n1 = int(num[i + 1:j + 1:])\n",
    "                    if str(n1) != num[i + 1:j + 1:] or n>2**31: break\n",
    "                    for k in range(j + 1, len(num)):\n",
    "                        n2 = int(num[j + 1:k + 1:])\n",
    "                        if str(n2) != num[j + 1:k + 1:] or n>2**31: break\n",
    "                        tnum = num[len(str(n))+len(str(n1))::]\n",
    "                        if n + n1 == n2:\n",
    "                            if k + 1 == len(num):\n",
    "                                path.append([n2, tnum, True,[n,n1,n2]])\n",
    "                            else:\n",
    "                                path.append([n2, tnum, False,[n,n1]])\n",
    "                                break\n",
    "        else:\n",
    "            num = p[1]\n",
    "            # num = num[len(str(p[0]))::]\n",
    "            n=p[-1][-2]\n",
    "            n1=p[-1][-1]\n",
    "            for k in range(len(num)):\n",
    "                n2 = int(num[:k + 1:])\n",
    "                if str(n2) != num[:k + 1:] or n2>2**31: break\n",
    "                if n + n1 == n2:\n",
    "                    tnum = num[len(str(n2)) ::]\n",
    "                    tp=p[3][:]\n",
    "                    tp.append(n2)\n",
    "                    if k + 1 == len(num):\n",
    "                        path.append([n2, tnum, True,tp])\n",
    "\n",
    "                    else:\n",
    "                        path.append([n2, tnum, False,tp])\n",
    "                    break\n",
    "                elif n + n1 < n2:\n",
    "                    break\n",
    "\n",
    "        return path\n",
    "\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        path=self.GetF(['',num,False,[]])\n",
    "        while True:\n",
    "            if len(path) == 0: break\n",
    "            r=[]\n",
    "            for item in path:\n",
    "                if item[2]:\n",
    "                    return item[3]\n",
    "                r+=self.GetF(item)\n",
    "            path=copy.deepcopy(r)\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\r\n",
    "\r\n",
    "        l=len(num)\r\n",
    "        if l<3:\r\n",
    "            return []\r\n",
    "        nums=list(map(int,num))\r\n",
    "        if l==3:\r\n",
    "            return nums[0]+nums[1]==nums[2]\r\n",
    "\r\n",
    "        ret=[]\r\n",
    "        Max=2**31\r\n",
    "        def dfs(idx,path:list):\r\n",
    "            nonlocal l,ret\r\n",
    "            if ret:\r\n",
    "                return\r\n",
    "            if idx==l:\r\n",
    "                if len(path)>2:\r\n",
    "                    ret=path.copy()\r\n",
    "                return\r\n",
    "            \r\n",
    "            if len(path)<2:\r\n",
    "                if nums[idx]==0:\r\n",
    "                    path.append(0)\r\n",
    "                    dfs(idx+1,path)\r\n",
    "                    path.pop()\r\n",
    "                    return\r\n",
    "                cur=0\r\n",
    "                for i in range(idx,l):\r\n",
    "                    cur=cur*10+nums[i]\r\n",
    "                    path.append(cur)\r\n",
    "                    dfs(i+1,path)\r\n",
    "                    path.pop()\r\n",
    "                return\r\n",
    "            target=path[-2]+path[-1]\r\n",
    "            if target>=Max:\r\n",
    "                return\r\n",
    "            if nums[idx]==0:\r\n",
    "                if target==0:\r\n",
    "                    path.append(0)\r\n",
    "                    dfs(idx+1,path)\r\n",
    "                    path.pop()\r\n",
    "                return\r\n",
    "            cur=0\r\n",
    "            for i in range(idx,l):\r\n",
    "                cur=cur*10+nums[i]\r\n",
    "                if cur==target:\r\n",
    "                    path.append(target)\r\n",
    "                    dfs(i+1,path)\r\n",
    "                    path.pop()\r\n",
    "                if cur>=target:\r\n",
    "                    return\r\n",
    "        dfs(0,[])\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def dfs(lst, num_):\n",
    "            if num_ == \"\": \n",
    "                return lst, \"\"\n",
    "            if len(lst) <= 1:\n",
    "                if num_[0] == '0': return dfs(lst + [0], num_[1:]) \n",
    "                for i in range(1, len(num_) - 1):\n",
    "                    lst_, s = dfs(lst + [int(num_[:i])], num_[i:])\n",
    "                    if s == \"\": return lst_, s \n",
    "            else:\n",
    "                x = lst[-2] + lst[-1]\n",
    "                if x < 1 << 31 and num_.startswith(s_ := str(x)):\n",
    "                    #print(lst + [x], num_[len(str(x)): ])\n",
    "                    return dfs(lst + [x], num_[len(s_): ])\n",
    "            return lst, num_\n",
    "        lst, s = dfs([], num)\n",
    "        #print(lst, s)\n",
    "        return [] if s else lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        res = []\n",
    "        def hh(index):\n",
    "            print(index, res)\n",
    "            if index == len(num):\n",
    "                return len(res) >= 3\n",
    "            n = 0\n",
    "            for i in range(index, len(num)):\n",
    "                if i > index and num[index] == '0':\n",
    "                    break\n",
    "                n = n * 10 + int(num[i])\n",
    "                if n >= 2 ** 31:\n",
    "                    break\n",
    "                if len(res) < 2 or n == res[ - 1] + res[ - 2]:\n",
    "                    res.append(n)\n",
    "                    if hh(i + 1):\n",
    "                        return True\n",
    "                    res.pop()\n",
    "                elif len(res) > 2 and n > res[ - 1] + res[ - 2]:\n",
    "                    break\n",
    "            return False       \n",
    "        hh(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        MN, MX = -2**31 , 2**31 -1\n",
    "        \n",
    "        def dfs(i, p):\n",
    "            # print(p)\n",
    "            if i == n:\n",
    "                if len(p) > 2:\n",
    "                    ans.append(p)\n",
    "                return\n",
    "            if len(p) < 2:\n",
    "                if num[i] == '0':\n",
    "                    dfs(i+1, p + [0])\n",
    "                else:\n",
    "                    for j in range(i+1, n+1):\n",
    "                        if MN <=int(num[i:j])<=MX:\n",
    "                            dfs(j, p + [int(num[i:j])])\n",
    "            else:\n",
    "                for j in range(i+1, n+1):\n",
    "                    a, b = p[-2], p[-1]\n",
    "                    if a > 0 and b > 0 and num[i] == '0':\n",
    "                        break\n",
    "                    if int(num[i:j]) == a + b and MN <=int(num[i:j])<=MX:\n",
    "                        dfs(j, p + [int(num[i:j])])\n",
    "                    elif int(num[i:j]) > a + b:\n",
    "                        break\n",
    "        \n",
    "        \n",
    "        ans = []\n",
    "        dfs(0, [])\n",
    "        return [] if not ans else ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        mx, n, ans = 2 ** 31, len(num), []\n",
    "        if n < 3: return 0\n",
    "        def get(idx, v1, v2):\n",
    "            if idx == n: return True\n",
    "            if num[idx] == '0':\n",
    "                if v1 == v2 == 0:\n",
    "                    ans.append(0)\n",
    "                    if get(idx + 1, 0, 0): return True\n",
    "                    ans.pop()\n",
    "                return False\n",
    "            else:\n",
    "                v = v1 + v2\n",
    "                l = len(str(v))\n",
    "                if v > mx or idx + l > n: return False\n",
    "                v3 = int(num[idx: idx + l])\n",
    "                if v3 != v: return False\n",
    "                ans.append(v3)\n",
    "                if get(idx + l, v2, v3): return True\n",
    "                ans.pop()\n",
    "                return False\n",
    "        if num[0] == '0':\n",
    "            ans.append(0)\n",
    "            if num[1] == '0':\n",
    "                ans.append(0)\n",
    "                if get(2, 0, 0): return ans\n",
    "                ans.pop()\n",
    "            else:\n",
    "                for i in range(1, n - 1):\n",
    "                    v2 = int(num[1: i + 1])\n",
    "                    ans.append(v2)\n",
    "                    if v2 > mx: return []\n",
    "                    if get(i + 1, 0, v2): return ans\n",
    "                    ans.pop()\n",
    "            return []\n",
    "        for i in range(n - 2):\n",
    "            v1 = int(num[: i + 1])\n",
    "            ans.append(v1)\n",
    "            if v1 > mx:\n",
    "                ans.pop()\n",
    "                break\n",
    "            if num[i + 1] == '0':\n",
    "                ans.append(0)\n",
    "                if get(i + 2, v1, 0): return ans\n",
    "                ans.pop()\n",
    "            else:\n",
    "                for j in range(i + 1, n - 1):\n",
    "                    v2 = int(num[i + 1: j + 1])\n",
    "                    ans.append(v2)\n",
    "                    if v2 > mx:\n",
    "                        ans.pop()\n",
    "                        break\n",
    "                    if get(j + 1, v1, v2): return ans\n",
    "                    ans.pop()\n",
    "            ans.pop()\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        n = len(num)\n",
    "        if n < 3:\n",
    "            return result\n",
    "        \n",
    "        def dfs(num):\n",
    "            if len(result) >= 3 and result[-3] + result[-2] != result[-1]:\n",
    "                return False\n",
    "            if len(num) == 0 and len(result) >= 3 and result[-3] + result[-2] == result[-1]:\n",
    "                return True\n",
    "            n = len(num)\n",
    "            for i in range(1,n+1):\n",
    "                cur = num[:i]\n",
    "\n",
    "                if len(cur) >= 2 and cur[0] == '0':\n",
    "                    continue\n",
    "                if int(cur) > 2**31 -1:\n",
    "                    break\n",
    "                result.append(int(cur))\n",
    "                if dfs(num[i:]):\n",
    "                    return True\n",
    "                result.pop(-1)\n",
    "            return False\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        dfs(num)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        def dfs(lst, num_):\n",
    "            if num_ == \"\": \n",
    "                return lst, \"\"\n",
    "            if len(lst) <= 1:\n",
    "                if num_[0] == '0': return dfs(lst + [0], num_[1:]) \n",
    "                for i in range(1, len(num_) - 1):\n",
    "                    lst_, s = dfs(lst + [int(num_[:i])], num_[i:])\n",
    "                    if s == \"\": return lst_, s \n",
    "            else:\n",
    "                x = lst[-2] + lst[-1]\n",
    "                if x < 1 << 31 and num_.startswith(s_ := str(x)):\n",
    "                    #print(lst + [x], num_[len(str(x)): ])\n",
    "                    return dfs(lst + [x], num_[len(s_): ])\n",
    "            return lst, num_\n",
    "        lst, s = dfs([], num)\n",
    "        #print(lst, s)\n",
    "        return [] if s else lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, S: str) -> List[int]:\n",
    "        n = len(S)\n",
    "        self.res = []\n",
    "\n",
    "        def helper(start, tmp):\n",
    "            if start == n:\n",
    "                if len(tmp) > 2:\n",
    "                    self.res = tmp\n",
    "                return\n",
    "                \n",
    "            for i in range(start, n):\n",
    "                # 首位 0\n",
    "                if S[start] == \"0\" and i > start:\n",
    "                    break\n",
    "                num = int(S[start : i + 1])\n",
    "        \n",
    "                # 位数超限制\n",
    "                if num > 2 ** 31 - 1:\n",
    "                    break\n",
    "        \n",
    "                if len(tmp) < 2 or num == tmp[-1] + tmp[-2]:\n",
    "                    helper(i + 1, tmp + [num])\n",
    "        \n",
    "            return\n",
    "\n",
    "        helper(0, [])\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        def dfs(cur, i):\n",
    "            nonlocal ans\n",
    "            if len(ans):\n",
    "                return\n",
    "            if i == n:\n",
    "                if len(cur) >= 5:\n",
    "                    ans = cur[:]\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                s3 = num[i:j+1]\n",
    "                if len(s3) > 1 and num[i] == '0':\n",
    "                    break\n",
    "                if int(s3) >= (1 << 31):\n",
    "                    break\n",
    "                if cur[-1] == -1 or cur[-2] == -1 or cur[-1] + cur[-2] == int(s3):\n",
    "                    cur.append(int(s3))\n",
    "                    dfs(cur, j + 1)\n",
    "                    cur.pop()\n",
    "        cur = [-1,-1] \n",
    "        dfs(cur, 0)\n",
    "        print(f'{ans}')\n",
    "        return ans[2:] if len(ans) >= 5 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitIntoFibonacci(self, num: str) -> List[int]:\n",
    "        #回溯算法\n",
    "        path=[]\n",
    "        n=len(num)\n",
    "        def back(i):\n",
    "            if i==n:\n",
    "                return len(path)>=3\n",
    "            cur=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]==\"0\":\n",
    "                    break\n",
    "                cur=cur*10+int(num[j])\n",
    "                if cur>2**31-1:\n",
    "                    break\n",
    "                if len(path)<2 or cur==path[-1]+path[-2]:\n",
    "                    path.append(cur)\n",
    "                    if back(j+1):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                elif len(path)>2 and cur>path[-1]+path[-2]:\n",
    "                    break\n",
    "            return False\n",
    "        flag=back(0)\n",
    "        return path if flag else []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
